#pragma once

#include <deque>
#include <string>

namespace jianzhi_037
{

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x, TreeNode* left = nullptr, TreeNode* right = nullptr)
            : val(x), left(left), right(right) {}

    ~TreeNode() {
        if (left)
            delete left;
        if (right)
            delete right;
    }
};

class Codec
{
public:
    std::string serialize(TreeNode* root)
    {
        if (root == nullptr)
            return "[]";
        std::string code = "[";

        std::deque<TreeNode*> queue{root};
        for (std::string line; !queue.empty(); ) {
            for (int i = queue.size(); i > 0; --i) {
                if (queue.front()) {
                    queue.push_back(queue.front()->left);
                    queue.push_back(queue.front()->right);
                    code += line + std::to_string(queue.front()->val) + ",";
                    line.clear();
                } else {
                    line += "null,";
                }
                queue.pop_front();
            }
        }
        if (code.back() == ',')
            code.pop_back();

        code += "]";
        return code;
    }

    TreeNode* deserialize(std::string data)
    {
        if (data == "[]")
            return nullptr;
        std::deque<TreeNode*> queue;
        auto next = data.cbegin() + 1;
        auto root = next_token(next);
        if (root)
            queue.push_back(root);
        while (!queue.empty()) {
            if (next != data.cend()) {
                queue.front()->left = next_token(next);
                if (queue.front()->left)
                    queue.push_back(queue.front()->left);
            }
            if (next != data.cend()) {
                queue.front()->right = next_token(next);
                if (queue.front()->right)
                    queue.push_back(queue.front()->right);
            }
            queue.pop_front();
        }
        return root;
    }

private:
    template <typename It>
    TreeNode* next_token(It& first)
    {
        if ((*first >= '0' && *first <= '9') || *first == '-' || *first == '+') {
            int sign = 1;
            auto node = new TreeNode(0);
            while (*first != ',' && *first != ']') {
                if (*first == '-') {
                    sign = -1;
                } else if (*first >= '0' && *first <= '9') {
                    node->val *= 10;
                    node->val += *first - '0';
                }
                ++first;
            }
            node->val *= sign;
            ++first;
            return node;
        } else {
            first += 5;
            return nullptr;
        }
    }
};

}  /* namespace jianzhi_037 */
